In recent years, the multi-state flow network (MFN) is widely used to simulate the systems in real world, such as computer network, supply chain system and power grid or transportation network. Therefore, the multi-state flow network is important for the current application and research and also attracts a broad attention of many researchers.
Reliability is one of the important indices for evaluating the performance of MFN. The definition of the reliability of the multi-state flow network generally is the probability of successfully transferring a required amount of flow, d, from the source node to the reception node. Please refer to FIG. 1, the connected graph, G(V, E, W), shown in FIG. 1 is used for describe the multi-state flow network, comprising a node set V={1, 2, . . . , n}, an arc set E={e1, e2, . . . , em}, and a vector set W=(w1, w2, . . . , wm) which indicates the max-capacity of each arc, wherein 1 denotes the source node, n denotes the reception nodes (n equals to the number of the nodes). Using FIG. 1 as an example, there are four nodes in a multi-state flow network, which are the source node {circle around (1)}, the reception node {circle around (4)}, the connection nodes {circle around (2)} and {circle around (3)}, respectively. The arc e1 connects the source node {circle around (1)} to the connection node {circle around (2)} and its max-capacity is 3. The arc e6 connects the connection node {circle around (3)} to the reception node {circle around (4)} and its max-capacity is 2. In other cases, this will not repeat them, and so on.
It can be known from FIG. 1, for a multi-state flow network, there are many paths of transferring a required amount of flow from the source node {circle around (1)}, through the connection nodes {circle around (2)} and {circle around (3)}, to the reception node {circle around (4)}. Each path can be represented by a system-state vector d-MP, for example, 3-MP represents the given flow upper limit as 3 of the multi-state flow network transferring from the source node {circle around (1)} to the reception node {circle around (4)}. All the d-MP of the multi-state flow network are denoted by P1, P2, . . . , Pn. In addition, each node follows the flow conservation law, i.e., the received amount of flow must equal to the output amount of flow.
Accordingly, the current technique proposed the sum of disjoint products (SDP) technique to calculate the reliability of a multi-state flow network. Suppose that the multi-state flow network is 3-MP, and has three system-state vectors, which means that, in the multi-state flow network, there are three states being able to successfully transfer amount of flow of 3 from the source node to the reception node, for example, P1=(3,2,1,0,0,1), P2=(2,2,0,0,1,1), and P3=(2,1,1,0,1,2). In the system-state vector P1, 3 units amount of flow can be transferred from the source node {circle around (1)} to the connection node {circle around (2)}, units amount of flow can be transferred from the connection node {circle around (2)} to the reception node {circle around (4)}, unit amount of flow can be transferred from the connection node {circle around (2)} to the connection node {circle around (3)}, the amount of flow from the connection node {circle around (3)} to the connection node {circle around (2)} as well as the source node {circle around (1)} to the connection node {circle around (3)} are both zero, and the connection node {circle around (3)} transfers 1 unit amount of flow to the reception node {circle around (4)}. So on for the system-state vectors P2 and P3, this will not repeat them.
Refer to the following Table 1, for example. In the system-state vector P1, the probability of that the source node {circle around (1)} transfers 3 units amount of flow to the connection node {circle around (2)} is 0.6, the probability of that the connection node {circle around (2)} transfers 2 units amount of flow to the reception node {circle around (4)} is 0.6, the probability of that 1 unit amount of flow transferred from the connection node {circle around (2)} to the connection node {circle around (3)} is 0.9, the probability of that the connection node {circle around (3)} transfers 0 unit amount of flow to the connection node {circle around (2)} is 0.1+0.9, the probability of that the source node {circle around (1)} transfers 0 unit amount of flow to the connection node {circle around (3)} is 0.1+0.9, and the probability of the connection node {circle around (3)} transfers 1 unit amount of flow to the reception node {circle around (4)} is 0.7+0.25. So on for the system-state vectors P2 and P3, this will not repeat them.
TABLE 1component, iPr({X(ei) = x|x = j})capacity, j1234560.05.10.10.10.10.051.10.30.90.90.90.252.25.60.703.60
The following is the procedure of reliability calculation of the multi-state flow network by SDP technique.
STEP 1.
            Let      ⁢                          ⁢      i        =    3                                            R            d                    =                    ⁢                                    Pr              ⁡                              (                                  P                  1                                )                                      +                          [                                                Pr                  ⁡                                      (                                          P                      2                                        )                                                  -                                  Pr                  ⁡                                      (                                          P                      21                                        )                                                              ]                                                                    =                    ⁢                                    Pr              ⁡                              (                                  3                  ,                  2                  ,                  1                  ,                  0                  ,                  0                  ,                  1                                )                                      +                          [                                                Pr                  ⁡                                      (                                          2                      ,                      2                      ,                      0                      ,                      0                      ,                      1                      ,                      1                                        )                                                  -                                  Pr                  ⁡                                      (                                          3                      ,                      2                      ,                      1                      ,                      0                      ,                      1                      ,                      1                                        )                                                              ]                                                                                =                        ⁢            .46683                    ,                          where    ,                  ⁢                                                      Pr              ⁡                              (                                  P                  1                                )                                      =                        ⁢                          Pr              (                              {                                                      X                    |                                          P                      1                                                        =                                                            (                                              3                        ,                        2                        ,                        1                        ,                        0                        ,                        0                        ,                        1                                            )                                        ≤                    X                                                  }                                                                                      =                        ⁢                                          p                13                            ·                              p                22                            ·                              p                31                            ·                              p                40                            ·                              p                50                            ·                              p                61                                                                                      =                        ⁢                                          (                .6                )                            ·                              (                .6                )                            ·                              (                .9                )                            ·                              (                                  .1                  +                  .9                                )                            ·                              (                                  .1                  +                  .9                                )                            ·                              (                                  .25                  +                  .7                                )                                                                                                    =                            ⁢              .3078                        ,                                                  Pr        ⁡                  (                      P            2                    )                    =                                    (                          .25              +              .6                        )                    ·          .6          ·                      (                          .1              +              .9                        )                    ·                      (                          .1              +              .9                        )                    ·          .9          ·                      (                          .25              +              .7                        )                          =        .43605              ,                  ⁢                                                      P              21                        =                        ⁢                          (                                                P                  1                                ⋂                                  P                  2                                            )                                                                        =                        ⁢                                          (                                  3                  ,                  2                  ,                  1                  ,                  0                  ,                  0                  ,                  1                                )                            ⋂                              (                                  2                  ,                  2                  ,                  0                  ,                  0                  ,                  1                  ,                  1                                )                                                                                      =                        ⁢                          (                                                Max                  ⁢                                      {                                          3                      ,                      2                                        }                                                  ,                                  Max                  ⁢                                      {                                          2                      ,                      2                                        }                                                  ,                                  Max                  ⁢                                      {                                          1                      ,                      0                                        }                                    ⁢                  Max                  ⁢                                      {                                          0                      ,                      0                                        }                                                  ,                                  Max                  ⁢                                      {                                          0                      ,                      1                                        }                                                  ,                                  Max                  ⁢                                      {                                          1                      ,                      1                                        }                                                              )                                                                                      =                            ⁢                              (                                  3                  ,                  2                  ,                  1                  ,                  0                  ,                  1                  ,                  1                                )                                      ,                                          Pr      ⁡              (                  P          21                )              =                  .6        ·        .6        ·        .9        ·                  (                      .1            +            .9                    )                ·        .9        ·                  (                      .25            +            .7                    )                    =              .27702        .            STEP2.j=2, D31={P3=(2,1,1,0,1,2)}, and D32={P31=(3,2,1,0,1,2), P32=(2,2,1,0,1,2)}.STEP 3.Because P31 and P32 are correlated (called sibling vectors), the procedure moves toward STEP4.STEP 4.
            Let      ⁢                          ⁢      j        =                  2        +        1            =      3        ,          ⁢                                          D            33                    =                    ⁢                      {                          Intersection              ⁢                                                          ⁢              of              ⁢                                                          ⁢                              P                31                            ⁢                                                          ⁢              and              ⁢                                                          ⁢                              P                32                            ⁢                                                          ⁢              in              ⁢                                                          ⁢                              D                32                                      }                                                        =                    ⁢                      {                                          P                31                            ⋂                              P                32                                      }                                                                    =                        ⁢                          {                                                P                  321                                =                                  (                                      3                    ,                    2                    ,                    1                    ,                    0                    ,                    1                    ,                    2                                    )                                            }                                ,                    
Move toward STEP 3 again.
STEP 3.
Because there is no correlated vectors in D33, the procedure moves toward STEP 5.
STEP 5.
  Let                                          R            d                    =                    ⁢                                    R              d                        +                          Pr              ⁡                              (                                  D                  3                                )                                                                                  =                    ⁢                      .411683            +                          [                                                Pr                  ⁡                                      (                                          P                      3                                        )                                                  -                                  Pr                  ⁡                                      (                                          P                      31                                        )                                                  -                                  Pr                  ⁡                                      (                                          P                      32                                        )                                                  +                                  Pr                  ⁡                                      (                                          P                      321                                        )                                                              ]                                                                    =                    ⁢                      .411683            +                          [                                                Pr                  ⁡                                      (                                          2                      ,                      1                      ,                      1                      ,                      0                      ,                      1                      ,                      2                                        )                                                  -                                  Pr                  ⁡                                      (                                          3                      ,                      2                      ,                      1                      ,                      0                      ,                      1                      ,                      2                                        )                                                  -                                                                                            ⁢                                    Pr              ⁡                              (                                  2                  ,                  2                  ,                  1                  ,                  0                  ,                  1                  ,                  2                                )                                      +                          Pr              ⁡                              (                                  3                  ,                  2                  ,                  1                  ,                  0                  ,                  1                  ,                  2                                )                                              ]                                              =                    ⁢                      .611415            .                              STEP 6.
i=3 equals to the number of all the system-state vectors, so the procedure is stopped.
From the above procedure, it is very complex to calculate the reliability of the multi-state flow network by SDP technique. It requires many summation and multiplication procedures and results in a long calculation time. Therefore, how to reduce the summation and multiplication procedures for calculating the reliability of the multi-state flow network, so as to improve the calculation performance is to present the anxious issues to be solved.